package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-16 23:52
 */
public class Bag {
    public static void main(String[] args) {
        int[]w={3,4,5};
        int[]v={6,4,8};
        System.out.println(bestBag(w, v, 10));
    }
    public static int bestBag(int []w,int []v,int weight){
        //检查有效性
        if(w.length==1&&w[0]>weight){
            return 0;
        }
       return process(w,v,0,0,weight);
    }
    //递归过程

    /**
     *
     * @param w 物品的重量数组
     * @param v 物品的价值数组
     * @param index 遍历的当前物品的序号
     * @param alWeight 当前所遍历过的物品中在选择放与不放之后的重量
     * @param weight 背包的容量
     * @return
     */
    private static int process(int[] w, int[] v, int index, int alWeight, int weight) {
        //判断出口
        if(alWeight>weight){
            return -1;
        }
        if(index==w.length){
            return 0;//成功
        }
        //第一种情况：当前节点上不放值(因为当前物品一旦加入到背包中，背包的总容量就超了)
        int value1=process(w, v, index+1, alWeight, weight);
        //第二种情况：当前结点放入值
        int value2Next=process(w, v, index+1, alWeight+w[index], weight);
        int value2=-1;
        if(value2Next!=-1){
            value2=value2Next+v[index];
        }
        //返回两种结果的最大值
        return Math.max(value1, value2);
    }
}
